class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        vector<int> dp(n);
        // dp[i]表示的是到第i间房，包括第i间房所能偷的最大金币数
        // 第i间房有两种状态
        // 1. 偷，dp[i] = nums[i] + dp[i - 2]
        // 2. 不偷，dp[i] = dp[i - 1]

        // 初始化dp数组
        // 第一间房，只能偷了，不偷就什么都没有，因为dp[0]表示到第0间房，包括第0间房所能偷的最大金币数
        // 第二间房，取第一间和第二间的较大值，因为如果第二间偷了，第一间是不能偷的
        // 比如[1, 3]，第二间房是3，dp[1]表示第1间房，包括第1间房所能偷的最大金币数
        // 如果不偷，dp[1]就是1，如果偷了，dp[1]就是3
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        // 状态转移方程
        // dp[i] = max(偷，不偷) ---> dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        for(int i = 2; i < n; i++)
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        return dp[n - 1];
    }
};